import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:龙宝
 * Date:2023-12-03
 * Time:10:40
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {1,4,2,6,8,9,7,5,3,0};
        Sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void Sort(int[] arr,int left,int right) {
        if(left < right) {
            //分
            int mid = (left + right) / 2;
            Sort(arr,left,mid);
            Sort(arr,mid+1,right);

            //治
            MergeSort1(arr,left,mid,right);
        }
    }

    private static void MergeSort1(int[] arr, int left, int mid, int right) {
        int i = left;
        int j = mid+1;
        int[] tmp = new int[right-left+1];
        int t = 0;
        while (i <= mid && j <= right) {
            while (i <= mid && j <= right && arr[i] < arr[j]) {
                tmp[t++] = arr[i++];
            }
            while (i <= mid && j <= right && arr[i] > arr[j]) {
                tmp[t++] = arr[j++];
            }

        }
        while (i <= mid) {
            tmp[t++] = arr[i++];
        }
        while (j <= right) {
            tmp[t++] = arr[j++];
        }
        t = 0;
        int tleft = left;
        for(i = 0;i<tmp.length;i++) {
            arr[tleft++] = tmp[t++];
        }
    }

}
